package pro.softzhang.algo.lc1100;

import pro.softzhang.algo.common.Utils;

/**
 *
 */
public class LC1122_RelativeSortArray {
    public static void main(String[] args) {
        int[] arr1 = new int[]{2,3,1,3,2,4,6,7,9,2,19}, arr2 = new int[]{2,1,4,3,9,6};
        int[] result = new Solution().relativeSortArray(arr1, arr2);
        Utils.printArr(result);
    }

    static class Solution {
        public int[] relativeSortArray(int[] arr1, int[] arr2) {
            int[] count = new int[1001];

            for (int num : arr1) {
                count[num]++;
            }

            int idx = 0;
            for (int num : arr2) {
                while (count[num] > 0) {
                    arr1[idx++] = num;
                    count[num]--;
                }
            }

            for (int i = 0; i < count.length; i++) {
                while (count[i] > 0) {
                    arr1[idx++] = i;
                    count[i]--;
                }
            }

            return arr1;
        }
    }
}
